package com.zhugang.week06;

/**
 * @program algorithms
 * @description: isBalanced
 * @author: chanzhugang
 * @create: 2022/07/14 17:38
 */
public class IsBalanced {

    /**
     * 剑指offer 55-II 平衡二叉树
     * <p>
     * 返回值并非要求解的值，要求解的值放全局变量中
     *
     * @param root
     * @return
     */

    private boolean balanced = true;

    public boolean isBalanced(TreeNode root) {
        // 任意左右子树的深度差不超过1
        // 求左右子树的高度
        height(root);
        return balanced;
    }

    private int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (balanced == false) {
            // 优化:提前终止递归
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        if (Math.abs(leftHeight - rightHeight) > 1) {
            balanced = false;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}